package com.algorithm.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的层次遍历
 */
public class BinaryTreeLevelOrder {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> ll = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        int count = 1;

        while(!qu.isEmpty()){
            List<Integer> childList = new ArrayList<>();
            int tempCount = 0;
            for (int i = 0; i < count; i++) {
                TreeNode tn = qu.poll();
                if (tn != null) {
                    childList.add(tn.val);
                    qu.offer(tn.left);
                    qu.offer(tn.right);
                    tempCount += 2;
                }
            }
            if (!childList.isEmpty()) {
                ll.add(childList);
            }
            count = tempCount;
        }
        return ll;
    }

}
